﻿// Matrix POJ - 3685.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;


//血的教训 列固定 行是递增函数
//行固定 列不是递减函数
// 
//https://vjudge.csgrandeur.cn/problem/POJ-3685
/*
描述
给定一个 N × N 矩阵 A，其中第 i 行和第 j 列的元素 Aij 是一个数，它等于 i² + 100000 × i + j² - 100000 × j + i × j，你需要找出矩阵中第 M 小的元素。

输入
输入的第一行是测试用例的数量。
对于每个测试用例，只有一行包含两个整数，N（1 ≤ N ≤ 50,000）和 M（1 ≤ M ≤ N × N）。每个测试用例前都有一个空行。

输出
对于每个测试用例，将答案输出在一行上。

示例输入
输入样例：
12

1 1

2 1

2 2

2 3

2 4

3 1

3 2

3 8

3 9

5 1

5 25

5 10
输出样例：
3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
*/

const long long N = 50000;
long long t;
long long m, n;

long long calc(long long x, long long y) {
	if (x == 0) return -(1e12 + 10);
	if (x == n + 1) return (1e12 + 10);

	long long res = x * x + y * y + (x - y) * 100000LL + x * y;
	return res;
}

long long check(long long x) {
	long long ans = 0;
	for (long long i = 1; i <= n; i++) {
		long long l = 0;  long long r = n + 1LL;
		while (l < r) {
			long long mid = (l + r + 1LL) >> 1LL;
			if (calc(mid, i) <= x) {
				l = mid;
			}
			else {
				r = mid - 1LL;
			}
		}
		ans += (l);
		//cout << "# i = " << i <<" .res = " << ans << ". ";
	}

	return ans;
}


void solve() {
	long long r = 1e12;
	long long  l = -r;
	while (l < r) {
		long long mid = (l + r) >> 1ll;
		//mid = 123456789;
		if (check(mid) >= m) {
			r = mid;
		}
		else {
			l = mid + 1LL;
		}
	}

	cout << l << endl;
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> m;
		solve();
	}

	return 0;
}

